package lhc.alg.top100;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * description: https://leetcode.cn/problems/add-two-numbers-ii/
 *  直接放栈里 在进位加
 * author: hongchen.liao
 * date:  2022/8/14
 */
public class _445_Add_Two_Numbers_II {



     //Definition for singly-linked list.
     public class ListNode {
         int val;
         ListNode next;
         ListNode() {}
         ListNode(int val) { this.val = val; }
         ListNode(int val, ListNode next) { this.val = val; this.next = next; }
     }

    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            Deque<Integer> stack1 = new ArrayDeque<>();
            Deque<Integer> stack2 = new ArrayDeque<>();
            while(l1 != null){
                stack1.push(l1.val);
                l1 = l1.next;
            }
            while(l2 != null){
                stack2.push(l2.val);
                l2 = l2.next;
            }
            int carry = 0;
            ListNode ans = null;
            while(!stack1.isEmpty() || !stack2.isEmpty() || carry > 0){
                int a = stack1.isEmpty() ? 0 : stack1.pop();
                int b = stack2.isEmpty() ? 0 : stack2.pop();
                int sum = carry + a + b;
                carry = sum / 10;
                int curr = sum % 10;
                ListNode currNode = new ListNode(curr);
                currNode.next = ans;
                ans = currNode;
            }
            return ans;
        }
    }

}
